class Solution {
    public int searchInsert(int[] nums, int target) {
        int pos = 0;
        if (target < nums[0]) return 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                pos = i;
                break;
            }
            if (i > 0 && nums[i - 1] < target && nums[i] > target) {
                pos = i;
                break;
            }
            pos = i + 1;
        }
        return pos;
    }

    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}